package data_structur.LinkList;

/**
 * 1.构建环形单向链表思路：先创建第一个节点first，first指向该链表；
 *                       创建真正的第一个节点时，覆盖first；
 *                       后续加入每个新节点的next指向first。
 * 2.遍历思路：需要辅助节点cur，记录最后的节点，始终指向first；
 *            通过while遍历，结束条件为cur.next == first。
 * 约瑟夫问题：约瑟夫问题是个有名的问题。N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。
 *            例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
 */
public class JosephQuestionDemo {

    public static void main(String[] args) {
        CircleSingleLinkList circleSingleLinkList = new CircleSingleLinkList();
        circleSingleLinkList.showBoys();
        circleSingleLinkList.addBoy(25);
        System.out.println("\n"+circleSingleLinkList.getSize());
        circleSingleLinkList.showBoys();
        circleSingleLinkList.josephKillBoys(1, 3);
    }

}

/**
 * 环形单向链表
 */
class CircleSingleLinkList {

    public Boy first = new Boy(-1);

    public Boy getFirst() {
        return first;
    }

    public int getSize(){
        Boy cur = getFirst();
        int size = 0;
        do {
            ++size;
            cur = cur.getNext();
        } while (cur != first);
        return size;
    }

    // 增加num个Boy
    public void addBoy(int num){
        if (num < 1) {
            System.out.println("Num is too small, failed to add boys. ");
            return;
        }
        Boy cur = null;
        for (int i = 1; i <= num; i++){
            Boy boy = new Boy(i);
            if (i != 1){
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy;
            } else {
                first = boy;
                first.setNext(first);
                cur = first;
            }
        }
        System.out.println("--- ADD SUCCESS ---");
    }

    // 遍历显示Boy们
    public void showBoys(){
        System.out.println("\n↓↓↓BoysList↓↓↓");
        if (first.getNext() == null){
            System.out.println("↑↑↑BoysList↑↑↑\n");
            return;
        }
        Boy boy = first;
        do {
            System.out.println(boy);
            boy = boy.getNext();
        } while (boy != first);
        System.out.println("↑↑↑BoysList↑↑↑\n");
    }

    // 解决乔瑟夫问题
    // 思路：创建辅助指针helper，事先应指向最后一个节点，报数前先让first和helper移动k-1次
    //      当报数时，让first和helper同时移动m-1次
    //      将first指向的boy杀死
    public void josephKillBoys(int start, int interval){
        System.out.println("\n↓↓↓Joseph Start↓↓↓");
        if (start > getSize() || interval > getSize() || start < 1 || interval < 1){
            System.out.println("Input value illegal.");
            System.out.println("↑↑↑Joseph End↑↑↑\n");
            return;
        }
        Boy helper = first;
        while (true){
            if (helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        for (int i = 0; i < start-1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        while (true){
            if (helper == first){
                break;
            }
            for (int j = 0; j < interval - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println("Boy" + first.getNum()+ "：被杀死");
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后存活Boy是：Boy" + helper.getNum());
        System.out.println("↑↑↑Joseph End↑↑↑\n");
    }

}

/**
 * 节点
 */
class Boy {

    private int num;
    private Boy next;

    public Boy(int num){
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString(){
        return "{Boy: [num: " + this.num + "]}";
    }
}